package com.fanshuai.algorithms.divide;

/**
 * 假设一个袋子中装有16枚硬币。16枚硬币中有且仅有一枚是伪造的，并且那枚伪币要较真的硬币轻些。
 * 现在考虑如何找出这个伪造的硬币，这里仅提供一台可用于比较两组硬币重量的天平。通过这台仪器，可以知道两组硬币的重量是否相同
 */
public class FindCoin {
    /**
     * 分治法解决  二分法
     * @param a
     * @return
     */
    public static int findCoin(int[] a) {
        return findCoin(a, 0, a.length - 1);
    }

    private static int findCoin(int[] a, int left, int right) {
        if (left == right) {
            return left;
        }

        int mid = (left + right) / 2;
        int leftIndex = findCoin(a, left, mid);
        int rightIndex = findCoin(a, mid + 1, right);

        if (a[leftIndex] < a[rightIndex]) {
            return leftIndex;
        } else {
            return rightIndex;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 1, 1, 1, 0, 1, 1, 1};
        System.out.println(findCoin(a));
    }
}
